package hdoj;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


//迷宫问题
public class MazeProblem {

	//首先从最简单的开始
	//知道起点，知道终点
	public static void main(String[] args) {
		MazeProblem object = new MazeProblem();
		// object.getRes();
//		object.getResII();
		object.getResIII();
	}
	
	public void getRes(){
		Scanner scanner = new Scanner(System.in);
		int m, n;
		char[][] maze;
		boolean[][] visited;
		while(scanner.hasNext()){
			minLength = Integer.MAX_VALUE;
			n = scanner.nextInt();
			m = scanner.nextInt();
			maze = new char[n][m];
			visited = new boolean[n][m];
			for (int i = 0; i < n; i++) {
				maze[i] = scanner.next().toCharArray();
			}
			dfs(0, 0, 0, maze, '1', visited);
			System.out.println(minLength);
		}
		scanner.close();
	}
	
	private static final int[][] dir = {{1, 0},{-1, 0},{0, 1},{0, -1}};
	
	private int minLength = Integer.MAX_VALUE;
	
	public void dfs(int x, int y, int length, char[][] maze, char obstacle, boolean[][] visited){
		if(x == maze.length - 1 && y == maze[0].length - 1){
			//到达终点
			System.out.println("length: " + length);
			minLength = Math.min(minLength, length);
			return;
		}
		for (int i = 0; i < dir.length; i++) {
			int nextX = x + dir[i][0];
			int nextY = y + dir[i][1];
			// System.out.println("nextX :" + nextX + " nextY: " + nextY);
			if(nextX < 0 || nextX >= maze.length || nextY < 0 || nextY >= maze[0].length
					|| maze[nextX][nextY] == obstacle || visited[nextX][nextY]){
				continue;
			}
			visited[nextX][nextY] = true;
			dfs(nextX, nextY, length + 1, maze, obstacle, visited);
			visited[nextX][nextY] = false;
		}
	}
	
	//接下来我们不知道起点的位置和终点的位置
	public void getResII(){
		Scanner scanner = new Scanner(System.in);
		int m, n;
		int testCase = scanner.nextInt();
		char[][] maze;
		boolean[][] visited;
		int startX = 0, startY = 0;
		for(int i = 1; i <= testCase; i++){
			minLength = Integer.MAX_VALUE;
			n = scanner.nextInt();
			m = scanner.nextInt();
			maze = new char[n][m];
			visited = new boolean[n][m];
			for (int j = 0; j < n; j++) {
				String string = scanner.next();
				int index = string.indexOf('S');
				if(startX == 0 && index != -1){
					startX = j;
					startY = index;
				}
				maze[j] = string.toCharArray();
			}
			bfs(startX, startY, 0, maze, 'E', '#', visited);
			if(minLength == Integer.MAX_VALUE){
				System.out.println(-1);
			}else{
				System.out.println(minLength);
			}
		}
		scanner.close();
	}
	
	//感觉超时了，使用bfs，或者使用记忆化搜索
	//参见leetcode SurroundRegions
	public void dfsII(int x, int y, int length, char[][] maze, char des, char obstacle, boolean[][] visited){
		if(maze[x][y] == des){
			//到达终点
			minLength = Math.min(minLength, length);
			return;
		}
		for (int i = 0; i < dir.length; i++) {
			int nextX = x + dir[i][0];
			int nextY = y + dir[i][1];
			// System.out.println("nextX :" + nextX + " nextY: " + nextY);
			if(nextX < 0 || nextX >= maze.length || nextY < 0 || nextY >= maze[0].length
					|| maze[nextX][nextY] == obstacle || visited[nextX][nextY]){
				continue;
			}
			visited[nextX][nextY] = true;
			dfsII(nextX, nextY, length + 1, maze, des, obstacle, visited);
			visited[nextX][nextY] = false;
		}
	}
	
	class Node{
		int x, y;
		int step;
		Node(int x, int y) {  
	        this.x = x;  
	        this.y = y;  
	    } 
	}
	
	public void bfs(int x, int y, int length, char[][] maze, char des, char obstacle, boolean[][] visited){
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(new Node(x, y));
		Node temp;
		while (!queue.isEmpty()){
			temp = queue.poll();
			if(maze[temp.x][temp.y] == des){
				minLength = temp.step;
				return;
			}
			for (int i = 0; i < dir.length; i++) {
				int nextX = temp.x + dir[i][0];
				int nextY = temp.y + dir[i][1];
				// System.out.println("nextX :" + nextX + " nextY: " + nextY);
				if(nextX < 0 || nextX >= maze.length || nextY < 0 || nextY >= maze[0].length
						|| maze[nextX][nextY] == obstacle || visited[nextX][nextY]){
					continue;
				}
				visited[nextX][nextY] = true;
				Node next = new Node(nextX, nextY);
				next.step = temp.step + 1;
				queue.add(next);
			}
		}
	}
	
	
	//接下来我们来转弯
	//HDU 1728 逃离迷宫
	//从迷宫的一个位置走到另外一个位置，迷宫中有些是空地，有些地方是障碍，必须绕行。
	//只能走到与它相邻的4个位置中,在行走过程中，不能走到迷宫外面去。
	//  我们假定给定的两个位置都是空地，初始时，所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。
	// 在给定转弯次数的条件下，能从一个位置走到另外一个位置吗
	
	public void getResIII(){
		Scanner scanner = new Scanner(System.in);
		int m, n;
		int testCase = scanner.nextInt();
		char[][] maze;
		boolean[][] visited;
		int startX = 0, startY = 0;
		int endX, endY;
		for(int i = 1; i <= testCase; i++){
			minLength = Integer.MAX_VALUE;
			n = scanner.nextInt();
			m = scanner.nextInt();
			maze = new char[n][m];
			visited = new boolean[n][m];
			for (int j = 0; j < n; j++) {
				maze[j] = scanner.next().toCharArray();
			}
			int k = scanner.nextInt();
			startY = scanner.nextInt();
			startX = scanner.nextInt();
			endY = scanner.nextInt();
			endX = scanner.nextInt();
			bfsIII(--startX, --startY, --endX, --endY, 0, k, maze, '*', visited);
		}
		scanner.close();
	}
	
	
	class NodeIII{
		int x, y;
		int curve;
		
		public NodeIII() {
		}
		NodeIII(int x, int y) {  
	        this.x = x;  
	        this.y = y;  
	    } 
	}
	
	//这道题的关键是转弯，融合了深度搜索的广度优先搜索
	//Runtime 468MS  c++ 提交时15MS(无语了)
	public void bfsIII(int x, int y, int endX, int endY, int length, int k, char[][] maze, char obstacle, 
			boolean[][] visited){
		
		//是否能够逃离
		boolean canLeave = false;
		Queue<NodeIII> queue = new LinkedList<>();
		NodeIII temp = new NodeIII(x, y);
		visited[x][y] = true;
		NodeIII next;
		//由于题意初始不管往哪个方向都不算转弯，所以初始为-1
		temp.curve = -1;
		queue.add(temp);
		while(!queue.isEmpty()){
			temp = queue.poll();
			if(temp.x == endX && temp.y == endY && temp.curve <= k){  
				//到达终点
				canLeave = true;
	            break;  
	        }
			next = new NodeIII();
			next.curve = temp.curve + 1;//因为前面搜完了一个方向，就肯定会拐弯，所以要+1，也因此起点的k初始化为-1;
			for (int i = 0; i < dir.length; i++) {
				int curX = temp.x + dir[i][0];
				int curY = temp.y + dir[i][1];
				
				//搜完一个方向 
				while (curX >= 0 && curX < maze.length && curY >= 0 && curY < maze[0].length
						&& maze[curX][curY] != obstacle){
					if (!visited[curX][curY]) {
						visited[curX][curY] = true;
						//注意这里的，如果改变了node的x，y，那么之前加入的node的x，y也会改变
						NodeIII cur = new NodeIII(curX, curY);
						cur.curve = next.curve;
						queue.add(cur);
					}
					//因为我们要判断转弯，所以我们就继续往该方向的前面走
					//如果遇到了终点，我们此时肯定将值加进去了，之后再出队的时候，一定会遇到该值
					//继续沿着该方向走
					curX += dir[i][0];
					curY += dir[i][1];
				}
			}
		}
		if(canLeave){
			System.out.println("yes");
		}else{
			System.out.println("no");
		}
	}

	//更多类似的问题可见NightmareHDU1072  类似开始有固定血量，然后加血，掉血逃离的迷宫
	//带钥匙的迷宫 AwayFromHDU1429
}
